[回顾并发基础] CopyOnWriteArrayList & ConcurrentHashMap

concurrent

字数统计: 2.3k阅读时长: 8 min

 2019/09/22  Share

CopyOnWriteArrayList：基于写时复制策略的线程安全的 List；

ConcurrentHashMap：由分段锁(jdk7)实现发展为 CAS+synchronized+红黑树(jdk8) 的线程安全的 Map；

并发List —— CopyOnWriteArrayList

描述

在很多应用场景中，读操作可能会远远大于写操作。由于读操作根本不会修改原有的数据，因此对于每次读取都进行加锁其实是一种资源浪费。为了将读取的性能发挥到极致，JDK中提供了CopyOnWriteArrayList类。读取是完全不用加锁的，并且写入也不会阻塞读取操作，只有写入和写入之间需要进行同步等待，这样便可以使读操作的性能就会大幅度提升。

并发包中的并发List 只有 CopyOnWriteArrayList。CopyOnWri teArray List 是一个线程安全的 ArrayList ，对其进行的修改操作都是在底层的一个复制的数组（快照）上进行的，也就是使用了写时复制策略。

实现

CopyOnWriteArrayList 有两个成员变量，lock 是用在写时锁的实现，数据则存储在 array 数组中。

/** The lock protecting all mutators */
final transient ReentrantLock lock = new ReentrantLock();

/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;

1. 初始化

public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class)
      elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
      elements = c.toArray();
      // c.toArray might (incorrectly) not return Object[] (see 6260652)
      if (elements.getClass() != Object[].class)
        elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    setArray(elements);
}

public CopyOnWriteArrayList(E[] toCopyIn) {
 	 setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

无参构造器创建了一个大小为 0 的Object数组作为 array 初始值。而有参构造器则是将数组或集合的副本作为 array 初始值。

2. 添加元素

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 1. 获取独占锁
    lock.lock();
    try {
      // 2. 获取 array
      Object[] elements = getArray();
      // 3. 复制 array 到新数组, 添加元素到新数组
      int len = elements.length;
      Object[] newElements = Arrays.copyOf(elements, len + 1);
      newElements[len] = e;
      // 4. 使用新数组替换添加前的数组
      setArray(newElements);
      return true;
    } finally {
      // 5. 释放独占锁
      lock.unlock();
    }
}

final Object[] getArray() {
 	 return array;
}

删除及修改同添加操作一样，首先获取独占锁以保证其他线程不能对 array 进行修改，之后再释放锁。

3. 获取指定位置元素

private E get(Object[] a, int index) {
    return (E) a[index];
}

public E get(int index) {
 	 return get(getArray(), index);
}

当用户调用get(x)时，有两步操作：1. 获取数组；2.依照数组下标获取值。如果在两部之间，另一个线程对数组有增/删/改操作，那么对get(x)不会有影响，因为步骤2操作的数组依然是之前的数组。这就是写时复制策略产生的弱一致性。

4. 迭代器

CopyOnWriteArrayList 的迭代器是弱一致性的，即返回迭代器后，其他线程对 list 的增删该操作对迭代器是不可见的。

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}

static final class COWIterator<E> implements ListIterator<E> {
    // Snapshot of the array 
    private final Object[] snapshot;
    // 数组下标
    private int cursor;

    // 构造函数
    private COWIterator(Object[] elements, int initialCursor) {
      cursor = initialCursor;
      snapshot = elements;
    }

    // 是否遍历结束
    public boolean hasNext() {
      return cursor < snapshot.length;
    }

    // 获取 next
    public E next() {
      if (! hasNext())
        throw new NoSuchElementException();
      return (E) snapshot[cursor++];
    }
    ...
}

COWIterator 对象的 snapshot 变量保存了当前 list 的内容， cursor 是遍历 list 时数据的下标。如果在遍历期间其他线程对该 list 进行修改，那么 snapshot 即表示为快照，因为增删改后数组被新数组替换了，而老数组被 snapshot 引用。

5. 应用场景

CopyOnWriteArrayList 仅适用于写操作非常少的场景，而且能够容忍读写的短暂不一致，即写入的新元素并不能立刻被遍历到。
此外，CopyOnWriteArrayList 迭代器是只读的，不支持增删改，迭代器遍历的仅仅是一个快照。

6. 重看COW

COW 适用于数据库连接池这种读操作远远多于修改操作的场景，它反映出3个很重要的分布式理念：读写分离；最终一致；使用额外空间解决办法冲突。

当然 COW 的弱点是很明显的：随着 CopyOnWriteArrayList 中元素的增加，其修改代价将越来越昂贵，在高性能的互联网应用中，这种操作很容易引起故障。设置合理的初始化值、减少扩容开销、使用批量添加减少容器复制次数都是值得考虑的性能优化点。

Linux中也存在CopyOnWrite技术，除了有名的文件系统Brtfs外，基本的fork命令也使用了这项技术。fork()之后，kernel把父进程中所有的内存页的权限都设为read-only，然后子进程的地址空间指向父进程。当父子进程都只读内存时，相安无事。当其中某个进程写内存时，CPU硬件检测到内存页是read-only的，于是触发页异常中断（page-fault），陷入kernel的一个中断例程。中断例程中，kernel就会把触发的异常的页复制一份，于是父子进程各自持有独立的一份。这项技术可以减少分配和复制大量资源时带来的瞬间延时，也可以减少不必要的资源分配。

ConcurrentHashMap在 JDK7 和 JDK8 中的实现有些许变化，不过很多材料谈的都是 JDK7 。ConcurrentHashMap本身实现也是十分复杂，包含注释大约 6000+ 行，相比之前的笔记，不会贴代码，主要关注它实现思路，细节层面不会非常细。

HashMap

回顾 ConcurrentHashMap 之前，国际惯例回顾下HashMap吧。JDK7中 HashMap 采用的是数组位桶+链表的方式，每个键值对封装在 Entry (static class Entry<K,V> implements Map.Entry<K,V>) 里面，而 HashMap 维持着 Entry 数组，这就是数组位桶；而 Entry 本身也有 next 属性指向下一个 Entry，这可以看作是单向链表。

get()方法通过hash()函数得到对应 bucket 的下标hash(k)&(table.length-1)，然后依次遍历冲突链表，通过key.equals(k)方法来判断是否是要找的那个 Entry。

put()方法先检查是否包含这个key，不包含则采用头插法(JDK8是尾插)，在链表头部插入新的 Entry。当然新增Entry可能导致HashMap的实际容量超过阈值，需要扩容。当Entry 的数量超过 capacity(当前容量)* load_factor 时，容器将自动扩容并重新哈希，哈希表将具有大约两倍的桶数。

HashMap 的扩容时机选在了插入之后判断阈值是否扩容，若后续无插入则浪费了。而 ConcurrentHashMap 的实现是在插入元素前就判断是否超过阈值。

而 JDK8 的实现最大改进就是链表元素数量超过一定值后，将其转为红黑树，避免大量节点存在链表上时的O(n)查找时间。所以说 JDK8 使用的是 数组位桶+链表/红黑树的形式。JDK8使用Node代替 Entry，Node 可以被扩展成TreeNode，如果 node 的数目多于 8 个，那么链表就会被转换成红黑树；如果 node 的数目小于 6个，那么红黑树就会被转换成链表。

HashMap 不支持并发，主要场景是多线程同时put时，如果同时触发了rehash操作，会导致 HashMap 中的链表中出现循环节点(一个线程 rehash 完毕，另一个线程还没开始)，进而使得后面 get 的时候出现死循环，CPU达到100%。

并发Map —— ConcurrentHashMap

JDK7

ConcurrentHashMap 使用分段锁技术，将数据分成一段一段的存储（分成一个个Segment，每个 Segment 包含HashEntry数组，Segment extends ReentrantLock本质上是一个可重入的互斥锁），当一个线程对 HashEntry 数组的数据进行修改时，必须获得与之对应的 Segment 锁，其他段的数据也能被其他线程访问。

get(): 对 key.hashCode 进行再散列，通过这个散列值取高位定位到正确的 Segment，再使用再散列值与数组长度减一相与定位 HashEntry。接着遍历该 HashEntry 链表。get 过程不需要加锁，get 方法里使用到的共享变量都定义成了volatile类型（如当前 Segment 的大小字段 count 以及存储值的 HashEntry 中的 value），Happens-before规定了对 volatile 字段的写入先于读操作，所以 get 操作总能拿到最新值。

put(): 首先定位到 Segment 获取锁，之后定位到 HashEntry 索引位置进行遍历，有重复 key 则替换，若没有则插入头部。需要注意的是，插入操作需先判断 HashEntry 数组是否超过容量需扩容，扩容时只会针对这个 Segment 进行，数组容量是原先两倍。

size(): 先尝试2次不加锁的统计各个 Segment 大小，如果统计过程中 count 变化（modCount，在 put / remove / clean 时加 1），采用加锁的方式统计所有Segment的大小。

JDK8

Reference

https://read.douban.com/reader/ebook/122245168/

《Java并发编程之美》

Next Post

[HikariCP] DBPool & JDBC基础
Previous Post

[回顾并发基础] 常用并发工具类

CATALOG

1. 并发List —— CopyOnWriteArrayList
1. 1.1. 描述
2. 1.2. 实现
2. HashMap
3. 并发Map —— ConcurrentHashMap
1. 3.1. JDK7
2. 3.2. JDK8
4. Reference

